package com.gitee.ywj1352.leecode;

import java.util.LinkedList;

/**
 * @author wenjie.yang on 2019/6/27.
 */
public class Hard {


    public static void main(String[] args) {
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            //去除右边所以得比当前小的指针
            while (!list.isEmpty()&&nums[list.peekLast()] <= nums[i]) {
                list.removeLast();
            }
            //添加角标
            list.addLast(i);
            //去除首位角标 往前 进一格
            if (list.getFirst() == i - k) {
                list.removeFirst();
            }
            // 窗口长度为k时 再保存当前窗口中最大值
            if (i - k +1 >= 0) {
                result[i - k + 1] = nums[list.getFirst()];
            }
        }
        return result;
    }

    /**
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出\
     * needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     *  haystack = "hello", needle = "ll"
     */
    public int strStr(String haystack, String needle) {
        if(needle== null){
            return 0;
        }
        return haystack.indexOf(needle);
    }


    /**
     * 查找 二叉树 最大深度
     * 找到最长 路径
     */
    public int longestUnivaluePath(TreeNode root) {
        if (root.val == 0){
            return 0;
        }
        int left = longestUnivaluePath(root.left);
        int right = longestUnivaluePath(root.right);
        return Math.max(left,right)+1;
    }


    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

}
